﻿//Sutherland-Hodgman 算法  逐边裁剪

using System;
using System.Collections.Generic;
using System.Drawing;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace lesson1
{
   

    public class OrderEdgeCutHelper
    {
        public static List<List<Point>> Cut(List<Point> subject, List<Point> clip)
        {
            List<List<Point>> result = new List<List<Point>>();

            for (int i = 0; i < clip.Count; i++)
            {
                int nextIndex = (i + 1) % clip.Count;
                Point clipStart = clip[i];
                Point clipEnd = clip[nextIndex];

                List<Point> input = subject;
                List<Point> output = new List<Point>();

                for (int j = 0; j < input.Count; j++)
                {
                    int nextVertexIndex = (j + 1) % input.Count;
                    Point subjectStart = input[j];
                    Point subjectEnd = input[nextVertexIndex];

                    if (IsInside(clipStart, clipEnd, subjectEnd))
                    {
                        if (!IsInside(clipStart, clipEnd, subjectStart))
                        {
                            output.Add(GetIntersection(clipStart, clipEnd, subjectStart, subjectEnd));
                        }
                        output.Add(subjectEnd);
                    }
                    else if (IsInside(clipStart, clipEnd, subjectStart))
                    {
                        output.Add(GetIntersection(clipStart, clipEnd, subjectStart, subjectEnd));
                    }
                }

                subject = output;
            }

            if (subject.Count > 0)
            {
                result.Add(subject);
            }

            return result;
        }

        private static bool IsInside(Point clipStart, Point clipEnd, Point testPoint)
        {
            return (clipEnd.X - clipStart.X) * (testPoint.Y - clipStart.Y) -
                   (clipEnd.Y - clipStart.Y) * (testPoint.X - clipStart.X) >= 0;
        }

        private static Point GetIntersection(Point clipStart, Point clipEnd, Point subjectStart, Point subjectEnd)
        {
            float dx1 = clipEnd.X - clipStart.X;
            float dy1 = clipEnd.Y - clipStart.Y;
            float dx2 = subjectEnd.X - subjectStart.X;
            float dy2 = subjectEnd.Y - subjectStart.Y;

            float denominator = dx1 * dy2 - dy1 * dx2;

            if (denominator == 0)
            {
                throw new InvalidOperationException("Lines are parallel or coincident");
            }

            float t = ((subjectStart.X - clipStart.X) * dy2 - (subjectStart.Y - clipStart.Y) * dx2) / denominator;

            return new Point((int)(clipStart.X + t * dx1), (int)(clipStart.Y + t * dy1));
        }
        public static bool IsConvexPolygon(List<Point> polygon)
        {
            int n = polygon.Count;
            if (n < 3)
            {
                // 一个多边形至少需要3个顶点
                return false;
            }

            bool sign = false;
            for (int i = 0; i < n; i++)
            {
                float dx1 = polygon[(i + 2) % n].X - polygon[(i + 1) % n].X;
                float dy1 = polygon[(i + 2) % n].Y - polygon[(i + 1) % n].Y;
                float dx2 = polygon[i].X - polygon[(i + 1) % n].X;
                float dy2 = polygon[i].Y - polygon[(i + 1) % n].Y;

                float crossProduct = dx1 * dy2 - dy1 * dx2;

                if (i == 0)
                {
                    sign = crossProduct > 0;
                }
                else if (sign != (crossProduct > 0))
                {
                    // 方向不一致，说明是凹多边形
                    return false;
                }
            }

            return true;
        }
    }
}
